package leetcode.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
 *
 * 二叉搜索树的定义如下：
 *
 * 任意节点的左子树中的键值都 小于 此节点的键值。
 * 任意节点的右子树中的键值都 大于 此节点的键值。
 * 任意节点的左子树和右子树都是二叉搜索树。
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
 * 输出：20
 * 解释：键值为 3 的子树是和最大的二叉搜索树。
 * 示例 2：
 *
 *
 *
 * 输入：root = [4,3,null,1,2]
 * 输出：2
 * 解释：键值为 2 的单节点子树是和最大的二叉搜索树。
 * 示例 3：
 *
 * 输入：root = [-4,-2,-5]
 * 输出：0
 * 解释：所有节点键值都为负数，和最大的二叉搜索树为空。
 * 示例 4：
 *
 * 输入：root = [2,1,3]
 * 输出：6
 * 示例 5：
 *
 * 输入：root = [5,4,8,3,null,6,3]
 * 输出：7
 *  
 *
 * 提示：
 *
 * 每棵树最多有 40000 个节点。
 * 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-sum-bst-in-binary-tree
 */
public class 二叉搜索子树的最大键值和 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static class LawNode{
        int val;
        boolean isLaw = false;
        LawNode left;
        LawNode right;
        LawNode(int x) { val = x; }
    }

    private static void giveLaw(TreeNode node, LawNode lnode){
        if (node.left != null && node.right != null){
            if (node.left.val < node.val && node.right.val > node.val){
                lnode.isLaw = true;
            }
        }else if (node.left != null){
            if (node.left.val < node.val){
                lnode.isLaw = true;
            }
        }else if (node.right != null){
            if (node.right.val > node.val){
                lnode.isLaw = true;
            }
        }else {
            lnode.isLaw = true;
        }
        if (node.right != null){
            LawNode n = new LawNode(node.right.val);
            lnode.right = new LawNode(node.right.val);
            giveLaw(node.right, lnode.right);
        }
        if (node.left != null){
            LawNode n = new LawNode(node.left.val);
            lnode.left = new LawNode(node.left.val);
            giveLaw(node.left, lnode.left);
        }
    }

    private static boolean getLaw(LawNode lnode){
        if (lnode.left != null){
            if (!getLaw(lnode.left)){
                lnode.isLaw = false;
            }
        }
        if (lnode.right != null){
            if (!getLaw(lnode.right)){
                lnode.isLaw = false;
            }
        }
        if (lnode.right == null && lnode.left == null){
            return lnode.isLaw;
        }
        return lnode.isLaw;
    }

    private static void findLaw(LawNode lnode, List<LawNode> l){
        if (lnode.isLaw){
            l.add(lnode);
        }else {
            if (lnode.right != null){
                findLaw(lnode.right, l);
            }
            if (lnode.left != null){
                findLaw(lnode.left, l);
            }
        }
    }

    private static int tmax = 0;
    private static int sum(LawNode node){
        if (node == null){
            return 0;
        }else {
            int t = sum(node.right) + sum(node.left) + node.val;
            tmax = tmax>t ? tmax : t;
            return t;
        }
    }

    public static int maxSumBST(TreeNode root) {
        LawNode lroot = new LawNode(root.val);
        giveLaw(root, lroot);
        getLaw(lroot);
        List<LawNode> l = new ArrayList<LawNode>();
        findLaw(lroot, l);
        int max = 0;
        for (LawNode n : l){
            tmax = 0;
            sum(n);
            max = max>tmax  ? max : tmax;
        }
        return max;
    }

    public static void main(String[] args){
        TreeNode a1 = new TreeNode(1);
        TreeNode a2 = new TreeNode(2);
        TreeNode a3 = new TreeNode(3);
        TreeNode a4 = new TreeNode(4);
        TreeNode a5 = new TreeNode(5);
        a1.left= a2;
        a1.right = a3;
        a3.left = a4;
        a3.right = a5;

        System.out.println(maxSumBST(a1));
    }
}
